1. Field of the Invention
The present invention relates to a round robin arbitration circuit for arbitrating requests that are issued from multiple processors, installed with memories, in an information processor.
2. Description of the Related Art
A round robin arbitration circuit according to a prior art for arbitrating requests issued from N request sources has a priority encoder. The priority encoder uses N priority patterns (from 0 to N-1) to assign different priorities to the requests.
After conducting arbitration to select one of the requests, the priority encoder selects, for the next arbitration, one of the N priority patterns that assigns the lowest priority to the request source whose request has just been selected.
This prior art causes live-lock due to the masking and priority changing of requests. The term "live-lock" means a situation in which, although the arbitration circuit is operating, the selection of a specific request waits to be arbitrated without being executed by the arbitration circuit and, therefore, the request is locked. The live-lock may last perpetually depending on the program.
A round robin arbitration circuit according to a prior art for arbitrating N requests has a register for storing one of N values and a priority encoder for selecting one of N priority patterns according to the value in the register. After assigning priorities to the N requests according to the priority pattern specified by the value in the register, the arbitration circuit updates the value in the register among the N values according to a predetermined order.
This prior art may prevent live-lock caused by the reason mentioned above. This prior art, however, cyclically uses the arbitration patterns. If a program to be executed has a loop that issues requests cyclically and if the cycle of the requests match with the cycle of the arbitration patterns, the program will cause live-lock.
It is required, therefore, to provide a round robin arbitration circuit capable of surely arbitrating requests that ask for a resource or a data bus without live-lock or deadlock.
Before describing the embodiments of the present invention, the prior art and the disadvantages thereof will be described with reference to the related figures.
FIG. 1 shows an arbitration technique of a priority encoder of a round robin arbitration circuit according to the prior art. There are N request sources, and the priority encoder has N priority patterns (from 0 to N-1) for assigning priorities to the N request sources, respectively.
After conducting arbitration to select one of the N request sources, the priority encoder selects, for the next arbitration, one of the N priority patterns that assigns the lowest priority to the request source that has just been selected. If, in FIG. 1, the priority encoder selects a priority pattern 0 to assign the highest priority to a request source 0 and the lowest priority to a request source N-1, it selects in the next arbitration a priority pattern N-1 to assign the lowest priority to the request source 0 that has received the highest priority in the preceding arbitration.
If several requests compete for a resource, some requests must be masked. For example, if several requests ask for the same memory, only one of the requests is made active and the others are masked. The masked requests are excluded from arbitration which is conducted among the other requests. This technique may cause live-lock.
This kind of live-lock will be explained with reference to FIG. 2. There are requests a, b, and c in which the requests a and b are repeatedly issued and the requests b and c ask for the same resource. Priorities assigned to these requests are as shown in each period.
In period 1, the requests a and b occur first, and therefore, the request a is selected according to a priority pattern of c&gt;a&gt;b.
In period 2, the request a selected in the period 1 is executed. The period 2 has a priority pattern of b&gt;c&gt;a with the selected request a having the lowest priority. Then, the request b is selected between the requests b and c.
In period 3, the request b selected in the period 2 is executed. During the execution of the request b, the request c is masked because it needs the same resource as the request b. The masked state is indicated with a dotted line in FIG. 2. This period 3 has a priority pattern of c&gt;a&gt;b with the request b selected in the period 2 having the lowest priority. Although the request c has the highest priority, the request a is selected because the request c is masked in the period 3.
In period 4, the request a selected in the period 3 is executed. The period 4 has a priority pattern of b&gt;c&gt;a with the request a selected in the period 3 having the lowest priority. As a result, the request b is selected in the period 4.
Thereafter, period 5 has the same state as the period 3. Then, the states of the periods 3 and 4 are repeated to cause live-lock. This kind of live-lock is caused by masking requests and changing priorities assigned to requests. The livelock may last perpetually depending on the program. If the requests a and b are issued from a polling loop of a program for detecting a change in a flag and if the request c is an access request to change the flag, the periods 3 and 4 will be repeated perpetually in the program.
A round robin arbitration circuit for arbitrating N requests according to a prior art will be explained. The arbitration circuit has a register for storing one of N values and a priority encoder for providing one of N priority patterns according to the value in the register. After assigning priorities to requests according to a priority pattern specified by the value in the register, the arbitration circuit updates the value in the register among the N values according to predetermined order.
This prior art may prevent the live-lock caused by the reasons mentioned above. This prior art, however, cyclically uses the priority patterns. If a program has a loop that cyclically issues requests for an exclusive right, and if the cycle of the requests is synchronous with the cycle of the priority patterns when the program is executed, live-lock will occur.
This type of livelock will be explained with reference to FIG. 3. Suppose that a device CPUa serving as a request source repeatedly uses a resource in a program, and a device CPU serving as another request source repeats a polling operation to detect a free time of the resource so that the device CPU may use the resource. If the device CPU can successfully use the resource, the repetitive use of the resource by the device CPUa is released.
If the polling operation by the device CPU is carried out while the device CPUa is using the resource, the device CPU will perpetually be unable to use the resource, to cause live-lock in which the devices CPUa and CPU endlessly loop.
The start and end of use of a given resource is controlled under a flag set in a memory shared by all devices (CPUs). Generally, accesses to the flag from the devices are arbitrated according to a round robin arbitration system, which intentionally disturbs the accesses not to cause live-lock. However, live-lock sometimes occurs due to the following two reasons:
(1) If the devices spontaneously access the flag without competition or without the influence of arbitration, the live-lock mentioned above will occur only when access timing based on a program matches with live-lock causing timing. This problem must be solved in the program.
(2) If accesses to the flag from the devices occur in a program loop and compete with one another and if the number of the accesses is equal to the number of priority patterns of the round robin arbitration system, arbitration will not disturb the selection of the priority patterns. As a result, the same access will always be selected in every cycle of the program loop. For example, in FIG. 3, only the device CPUa uses the resource and the device CPU is unable to detect a free time of the resource, and therefore, is unable to use the resource perpetually, to cause live-lock. This live-lock causes a problem that an exclusive right is not evenly distributed to request sources such as CPUs or any other devices.
If a request is masked on condition that a related request must be met first, live-lock will occur. For example, when updating blocks of a cache memory, a read request for a block and a discharge-write request for another block may be issued through separate request lines. In this case, it is preferable to process the read request before the write request in view of the performance of a system. Therefore, the write request is masked until the read request is processed.
If the highest priority is assigned to the masked write request, there will be no change in the priority patterns, to conduct fixed priority arbitration. If, at this moment, the read request that releases the masked write request has the lowest priority and if a request source that constantly issues requests is present at a higher priority position than the read request, the read request will not be selected perpetually. This kind of live-lock will occur when a CPU issues a write request for releasing an exclusive right flag and another CPU issues a test (read) and set request for the same flag, because the read request is selected before the write request for the flag.